package primary.array;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @Author Elephas
 * @Date 2022/1/7
 **/
/*
    两个数组的交集 II
 */
public class Intersect {
    public static void main(String[] args) {
        final int[] test01_1 = new int[]{4,9,5};
        final int[] test01_2 = new int[]{9,4,9,8,4};
        intersect2(test01_1,test01_2);

    }

    /*
        解法一：排序后归并比较，nums1长度为n,nums2长度为m,时间复杂度为o(mlogm+nlogn),空间复杂度为o(1)
     */
    public static int[] intersect(int[] nums1,int[] nums2){
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        int i=0,j=0;
        while (i < nums1.length && j < nums2.length){
            if(nums1[i]==nums2[j]){
                list.add(nums1[i]);
                i++;
                j++;

            }else if(nums1[i]<nums2[j]){
                i++;
            }else{
                j++;
            }
        }
        int[] result = new int[list.size()];
        for (i = 0; i < list.size(); i++) {
            result[i]=list.get(i);
        }
        return result;
    }

    /*
        解法二： 哈希表
            首先遍历第一个数组，得到第一个数组每个不同元素的数量，然后遍历第二个数组，
            对于第二个数组中每个元素，如果可以在哈希表中找到它，将其加入输出数组，然后哈希表中记录的数值减少1
            nums1长度为n，nums2长度为m，时间复杂度为o(n+m)，空间复杂度为o(n)
     */
    public static int[] intersect2(int[] nums1,int[] nums2){
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int num : nums1){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else{
                map.put(num,map.get(num)+1);
            }
        }
        for(int num :nums2){
            if(map.containsKey(num)){
                if(map.get(num)!=0){
                    // 如果出现重复元素，则将map对应元素值减少1
                    list.add(num);
                    map.put(num,map.get(num)-1);
                }
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i]=list.get(i);
        }
        return result;
    }
}
